/*============================================================================*/
/*                                                                            */
/*   =============                                                            */
/*   linked_list.c                                                            */
/*   =============                                                            */
/*                                                                            */
/*                                                                            */
/*   =============                                                            */
/*                                                                            */
/*   This file defines a new data type :                                      */
/*                                                                            */
/*      LinkedList                                                            */
/*      ----------                                                            */
/*                                                                            */
/*   and procedures and functions working on LinkedList object                */
/*                                                                            */
/*   =============================================================            */
/*   Be careful : a LinkedList argument is always supposed no NULL            */
/*   =============================================================            */
/*                                                                            */
/*      LinkedList LDLIST.Create(void)                                        */
/*      ------------------------------                                        */
/*          creates and returns an LinkedList object.                         */
/*                                                                            */
/*      void       LDLIST.AddInfo(LinkedList s, void *info)                   */
/*      ---------------------------------------------------                   */
/*          records the pointer to info in the linked list s.                 */
/*                                                                            */
/*      void *     LDLIST.ReadNextInfo(LinkedList s)                          */
/*      --------------------------------------------                          */
/*          allows to get the pointers to records in the linked list s        */
/*          Each call returns the next pointer recorded in the linked list.   */
/*          When the end of the linked list s is reached, the function        */
/*          returns a NULL pointer.                                           */
/*                                                                            */
/*      void       LDLIST.Rewind(LinkedList s)                                */
/*      --------------------------------------                                */
/*         rewinds the linked list s.                                         */
/*                                                                            */
/*      void       LDLIST.Size(LinkedList s)                                  */
/*      ------------------------------------                                  */
/*         returns the number of records in the linked list s.                */
/*                                                                            */
/*      void *     LDLIST.Find(LinkedList s, void *info,                      */
/*                             int (*compare)(void *, void *))                */
/*      ------------------------------------------------------                */
/*         determines whether or not the linked list s contains info          */
/*         If the function finds info, it returns its pointer                 */
/*         else it returns a NULL pointer.                                    */
/*         The third argument is a function allowing to compare info with     */
/*         records in the linked list s. It has to return 0 if info is found. */
/*                                                                            */
/*      LinkedList LDLIST.Free(LinkedList s, void (*delete)(void *))          */
/*      ------------------------------------------------------------          */
/*         frees all records of the linked list s,                            */
/*         frees linked list s and returns a NULL pointer.                    */
/*         The second argument is a procedure allowing to delete a record.    */
/*                                                                            */
/*============================================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "linked_list.h"

typedef struct _Node Node ;

struct _Node {
   void *info ;
   Node *next ;
} ;

struct _LinkedList {
   int   N ;
   Node *first ;
   Node *end   ;
   Node *current ;
} ;

/*============================================================================*/
/* Create                                                                     */
/*============================================================================*/
static LinkedList Create(void)
{
   LinkedList s ;

   if ((s = (LinkedList) malloc(sizeof(struct _LinkedList))) == NULL) {
      fprintf(stderr, "*** error *** file %s : string creation\n", __FILE__) ;
      exit(EXIT_FAILURE) ;
   }

   s->N     = 0 ;
   s->first = s->end = s->current = NULL ;

   return s ;
}

/*============================================================================*/
/* AddInfo                                                                    */
/*============================================================================*/
static void AddInfo(LinkedList s, void *info)
{
   Node *n ;

   if ((n = (Node *) malloc(sizeof(Node))) == NULL) {
      fprintf(stderr, "*** error *** file %s : node creation\n", __FILE__) ;
      exit(EXIT_FAILURE) ;
   }

   n->info = info ;
   n->next = NULL ;

   if (s->first == NULL)
      s->first = s->current = s->end = n ;
   else
      s->end->next = n ;
  
   s->end = n ;
   s->N++ ;
}

/*============================================================================*/
/* Rewind                                                                     */
/*============================================================================*/
static void Rewind(LinkedList s)
{
   s->current = s->first ;
}

/*============================================================================*/
/* Size                                                                       */
/*============================================================================*/
static int Size(LinkedList s)
{
   return s->N ;
}

/*============================================================================*/
/* ReadNextInfo                                                               */
/*============================================================================*/
static void *ReadNextInfo(LinkedList s)
{
   void *info ;
   Node *n ;

   if ((n = s->current) == NULL)
      return NULL ;

   info       = n->info ;
   s->current = n->next ;

   return info ;
}

/*============================================================================*/
/* Find                                                                       */
/*============================================================================*/
static void *Find(LinkedList s, void *keyword, int (*compare)(void *, void *))
{
   void *info ;

   LDLIST.Rewind(s) ;

   while ((info = LDLIST.ReadNextInfo(s))) {
      if (!compare(info, keyword))
         return info ;
   }

   return NULL ;
}

/*============================================================================*/
/* Free                                                                       */
/*============================================================================*/
static LinkedList Free(LinkedList s, void (*delete)(void *))
{
   Node *n, *next ;

     n = s->first ;

     while(n != NULL) {
       next = n->next ;
       delete(n->info) ;
       free(n) ;
       n = next ;
     }

     free(s) ;
     return NULL ;
}

struct _LDLIST LDLIST = 
   {Create, AddInfo, Rewind, Size, ReadNextInfo, Find, Free} ;


/*============================================================================*/
/* Test                                                                       */
/*============================================================================*/
#ifdef TEST_LINKEDLIST

#include <strings.h>

static int compare(void *x, void *y)
{
   return strcmp(x, y) ;
}

static void delete(void *x)
{
   free(x) ;
}

int main()
{
   int   i = 0 ;
   void *info  ;
   char  tuesday[] = "Tuesday", sunday[] = "Sunday" ;

   /*-------------------------------------------------------------------------*/
   /* create a LinkedList object s                                            */
   /*-------------------------------------------------------------------------*/
   LinkedList  s = LDLIST.Create() ;

   /*-------------------------------------------------------------------------*/
   /* initialize the LinkedList object s                                      */
   /*-------------------------------------------------------------------------*/
   LDLIST.AddInfo(s, strdup("Monday")) ;
   LDLIST.AddInfo(s, strdup("Tuesday")) ;
   LDLIST.AddInfo(s, strdup("Wednesday")) ;
   LDLIST.AddInfo(s, strdup("Thursday")) ;
   LDLIST.AddInfo(s, strdup("Friday")) ;

   /*-------------------------------------------------------------------------*/
   /* read records in the LinkedList object s                                 */
   /*-------------------------------------------------------------------------*/
   while ((info = LDLIST.ReadNextInfo(s)))
      printf("info %d : %s\n", ++i, info) ;

   /*-------------------------------------------------------------------------*/
   /* rewind the LinkedList object s                                          */
   /*-------------------------------------------------------------------------*/
   LDLIST.Rewind(s) ;

   /*-------------------------------------------------------------------------*/
   /* read again records in the LinkedList object s                           */
   /*-------------------------------------------------------------------------*/
   while ((info = LDLIST.ReadNextInfo(s)))
      printf("info %d : %s\n", ++i, info) ;

   /*-------------------------------------------------------------------------*/
   /* find Tuesday                                                            */
   /*-------------------------------------------------------------------------*/
   if ((info = LDLIST.Find(s, tuesday, compare)))
      printf("Tuesday found\n") ;
   else
      printf("Tuesday no found\n") ;

   /*-------------------------------------------------------------------------*/
   /* find Sunday                                                            */
   /*-------------------------------------------------------------------------*/
   if ((info = LDLIST.Find(s, sunday, compare)))
      printf("Sunday found\n") ;
   else
      printf("Sunday no found\n") ;

   /*-------------------------------------------------------------------------*/
   /* free the LinkedList object s and records                                */
   /*-------------------------------------------------------------------------*/
   LDLIST.Free(s, delete) ;

   return 0 ;
}
#endif /* TEST_LINKEDLIST */
